import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 1686. 石子游戏 VI
 * <a href="https://leetcode.cn/problems/stone-game-vi/">...</a>
 * User: DELL
 * Date: 2023-10-13
 * Time: 9:12
 */
public class Solution {
    private class Unit {
        int index;
        int value;

        public Unit(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

    /**
     * 解题思路: (贪心)
     * 本题我们应该考虑到如何选取石子才是最优的,即一方面使得自己获得的收益最大,
     * 同时也应该阻止对方获得较大的收益,即一个石子本身的收益应该是双方收益之和.
     * 例如 alice{2,3}, bob{4,1} 这种情况下 alice 选取第一个石子的收益
     * 为 2+4 (其中的 4 是阻止 bob 获得的收益),选取第二个石子的收益为 3+1;
     * 那么 alice 选取第一个石子即可以获胜,而若单单只考虑自己的收益选择第二个石子,
     * 则会输掉,即选取时应该考虑自己和对方的收益总和.
     * 那么问题就简单了,自定义一个类 Unit,其中两个属性分别为 index 和 value,
     * 然后初始化 units 数组,之后将 units 数组根据 value 从大到小排序即可,
     * 之后 alice 和 bob 依次获取最大的即可.
     * 自定义类有些冗余,也可以使用二维数组的方式,具体见如下第二种解法
     */
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int len = aliceValues.length;
        Unit[] units = new Unit[len];
        for (int i = 0; i < len; i++) {
            units[i] = new Unit(i, aliceValues[i] + bobValues[i]);
        }
        Arrays.sort(units, (u1, u2) -> u2.value - u1.value);
        int aliceSum = 0;
        int bobSum = 0;
        for (int i = 0; i < len; i++) {
            aliceSum += aliceValues[units[i].index];
            if (++i < len) {
                bobSum += bobValues[units[i].index];
            }
        }
        if (aliceSum > bobSum) {
            return 1;
        } else if (aliceSum == bobSum) {
            return 0;
        } else {
            return -1;
        }
    }

    public int stoneGameVI2(int[] aliceValues, int[] bobValues) {
        int len = aliceValues.length;
        int[][] temp = new int[len][2];
        for (int i = 0; i < len; i++) {
            temp[i][0] = i;
            temp[i][1] = aliceValues[i] + bobValues[i];
        }
        Arrays.sort(temp, (u1, u2) -> u2[1] - u1[1]);
        int aliceSum = 0;
        int bobSum = 0;
        for (int i = 0; i < len; i++) {
            aliceSum += aliceValues[temp[i][0]];
            if (++i < len) {
                bobSum += bobValues[temp[i][0]];
            }
        }
        if (aliceSum > bobSum) {
            return 1;
        } else if (aliceSum == bobSum) {
            return 0;
        } else {
            return -1;
        }
    }
}